package com.lims.algorithm.algset.graph.dijkstra;

import com.sun.deploy.util.StringUtils;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.stream.Stream;

/**
 * <描述:>
 *
 * @author lims
 * @date 2020-09-04 22:44
 */
public class GraphListDijkstra<T> {
    class Vertex<T> {
        // 数据
        T data;
        // 第一条边
        Edge firstEdge;
        // 入度
        int inDegree;
        // 出度
        int outDegree;

        public Vertex(T data, Edge firstEdge) {
            this.data = data;
            this.firstEdge = firstEdge;
        }

        // 入度加1
        public void incrInDegree() {
            inDegree++;
        }

        // 出度加1
        public void incrOutDegree() {
            outDegree++;
        }

        // 入度减1
        public void decrInDegree() {
            inDegree--;
        }

        // 出度减1
        public void decrOutDegree() {
            outDegree--;
        }
    }

    /**
     * 边 类
     */
    class Edge {
        // 指向的结点
        int pVex;
        // 下一条边
        Edge nextEdge;
        // 边权重
        int weight;

        public Edge(int pVex, Edge nextEdge, int weight) {
            this.pVex = pVex;
            this.nextEdge = nextEdge;
            this.weight = weight;
        }
    }

    /**
     * 最大值
     */
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 顶点集合
     */
    Vertex<T>[] vertexs;
    /**
     * 最大顶点数
     */
    int maxVerNum;
    /**
     * 顶点数
     */
    int verNum;
    /**
     * 是否访问
     */
    boolean[] isVisited;

    public GraphListDijkstra(int n) {
        maxVerNum = n;
        vertexs = (Vertex<T>[]) Array.newInstance(Vertex.class, n);
        isVisited = (boolean[]) Array.newInstance(boolean.class, n);
    }

    public void addVer(T ver) {
        if (verNum >= maxVerNum) {
            System.out.println("节点插满");
            return;
        }
        Vertex vertex = new Vertex(ver, null);
        vertexs[verNum++] = vertex;
    }

    public void addEdge(int v1, int v2, int weight) {
        Edge v1_2 = new Edge(v2, null, weight);

        Vertex<T> vertex = vertexs[v1];
        if (vertex.firstEdge == null) {
            vertex.firstEdge = v1_2;
        } else {
            Edge firstEdge = vertex.firstEdge;
            do {
                if (firstEdge.nextEdge == null) {
                    firstEdge.nextEdge = v1_2;
                    break;
                }
            } while ((firstEdge = firstEdge.nextEdge) != null);
        }

        vertexs[v1].incrOutDegree();
        vertexs[v2].incrInDegree();
    }

    public T getValue(int index) {
        return vertexs[index].data;
    }

    public void show() {
        System.out.println("邻接表显示：");
        Stream.iterate(0, t -> t + 1).limit(maxVerNum)
                .forEach(i -> {
                    System.out.printf("%d(%s):", i, getValue(i));
                    printLink(vertexs[i].firstEdge);
                    System.out.println();
                });
    }

    private void printLink(Edge first) {
        if (first == null) {
            return;
        }
        System.out.printf("->%d(%s)", first.pVex, getValue(first.pVex));
        printLink(first.nextEdge);
    }

    public void DFS() {
        System.out.println("深度优先遍历：");
        List<T> dfsResults = new ArrayList<>();
        for (int i = 0; i < vertexs.length; i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i, dfsResults);
            }
        }
        System.out.print(StringUtils.join(dfsResults, "->"));
        System.out.printf("\n");
    }

    private void DFS(boolean[] isVisited, int i, List<T> dfsResults) {
        dfsResults.add(getValue(i));
        isVisited[i] = true;
        int ajcVer = getNextAjcNoAccessVer(i);
        while (ajcVer != -1) {
            if (!isVisited[ajcVer]) {
                DFS(isVisited, ajcVer, dfsResults);
            }
            ajcVer = getNextAjcNoAccessVer(ajcVer);
        }
    }

    public void BFS() {
        System.out.println("广度优先遍历：");
        for (int i = 0; i < vertexs.length; i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void BFS(boolean[] isVisited, int i) {
        // 队列头
        int h;
        // 邻接点
        int ajcVer;
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        System.out.print(getValue(i));
        isVisited[i] = true;
        queue.offer(i);
        while (!queue.isEmpty()) {
            h = queue.poll();
            ajcVer = getNextAjcNoAccessVer(h);
            while (ajcVer != -1) {
                if (!isVisited[ajcVer]) {
                    System.out.print(" -> ");
                    System.out.print(getValue(ajcVer));
                    isVisited[ajcVer] = true;
                    queue.offer(ajcVer);
                }
                ajcVer = getNextAjcNoAccessVer(h);
            }
        }
    }

    public void clearIsVisited() {
        isVisited = new boolean[vertexs.length];
    }

    public int getNextAjcNoAccessVer(int index) {
        Vertex vertex = vertexs[index];
        Edge firstEdge = vertex.firstEdge;
        while (firstEdge != null) {
            if (!isVisited[firstEdge.pVex]) {
                return firstEdge.pVex;
            }
            firstEdge = firstEdge.nextEdge;
        }
        return -1;
    }


    /**
     * 拓扑排序 (tops[]：排序数组，inDegrees[]:入度数组，queue：辅助队列)
     * 1.入度0的入队列
     * 2.出队列访问，对邻接点入度-1，判断入度为0入队列
     *
     * @return
     */
    public int toplogicalSort() {
        List<T> tops;
        int[] inDegrees;
        Queue<Integer> queue = new LinkedBlockingQueue<>();

        tops = new ArrayList<>(maxVerNum);
        inDegrees = (int[]) Array.newInstance(int.class, maxVerNum);

        Stream.iterate(0, t -> t + 1).limit(maxVerNum)
                .forEach(i -> {
                    inDegrees[i] = vertexs[i].inDegree;
                    if (vertexs[i].inDegree == 0) {
                        queue.offer(i);
                    }
                });

        while (!queue.isEmpty()) {
            int h = queue.poll().intValue();
            tops.add(getValue(h));
            Edge firstEdge = vertexs[h].firstEdge;
            while (firstEdge != null) {
                if ((--inDegrees[firstEdge.pVex]) == 0) {
                    queue.offer(firstEdge.pVex);
                }
                firstEdge = firstEdge.nextEdge;
            }
        }

        if (tops.size() < inDegrees.length) {
            System.out.println("图中有环");
            return 1;
        }
        System.out.printf("拓扑排序结果：%s\n", tops);
        return 0;
    }

    /**
     * dijkstra最短路径
     *
     * @param v
     * @return
     */
    public int[] dijkstra(int v) {
        if (v < 0 || v > vertexs.length) {
            throw new ArrayIndexOutOfBoundsException();
        }

        // 确定距离标记数组
        boolean[] st = (boolean[]) Array.newInstance(boolean.class, vertexs.length);
        // 距离数组
        int[] distance = (int[]) Array.newInstance(int.class, vertexs.length);

        // 初始化距离数组，标记数组
        Edge curEdge = vertexs[v].firstEdge;
        while (curEdge != null) {
            distance[curEdge.pVex] = curEdge.weight;
            curEdge = curEdge.nextEdge;
        }
        // 对距离到不了的距离为无穷大
        Stream.iterate(0, t -> t + 1).limit(distance.length)
                .forEach(i -> distance[i] = (i != v ? (distance[i] != 0 ? distance[i] : INF) : 0));
        st[v] = true;

        // 循环判断 v ——> j 的最短距离
        Stream.iterate(0, t -> t + 1).limit(distance.length)
                .forEach(i -> {
                    int min = INF;
                    int index = -1;
                    // 1.找到未确定的最短距离
                    for (int j = 0; j < distance.length; ++j) {
                        if (!st[j] && distance[j] < min) {
                            min = distance[j];
                            index = j;
                        }
                    }

                    // 2.对确定index点影响了有出度的邻接点的最短距离，更新
                    if (index != -1) {
                        st[index] = true;
                        Edge firstEdge = vertexs[index].firstEdge;
                        while (firstEdge != null) {
                            // 到index的最短路径 + <index,邻接点> 是否小于 邻接点原始距离
                            if (!st[firstEdge.pVex] &&
                                    (min + firstEdge.weight) < distance[firstEdge.pVex]) {
                                distance[firstEdge.pVex] = min + firstEdge.weight;
                            }
                            firstEdge = firstEdge.nextEdge;
                        }
                    }
                });

        System.out.printf("最短距离（源点%d）:\n%s\n", v, Arrays.toString(distance));

        return distance;
    }


    public static void main(String[] args) {
        // 节点个数
        int n = 7;
        String[] vertexString = {"A", "B", "C", "D", "E", "F", "G"};
        GraphListDijkstra<String> dgList = new GraphListDijkstra<>(n);
        for (String s : vertexString) {
            dgList.addVer(s);
        }

        dgList.addEdge(0, 1, 10);
        dgList.addEdge(1, 2, 20);
        dgList.addEdge(2, 3, 30);
        dgList.addEdge(2, 4, 4);
        dgList.addEdge(0, 5, 1);
        dgList.addEdge(5, 6, 2);
        dgList.addEdge(6, 2, 3);

        dgList.show();

        dgList.DFS();
        dgList.clearIsVisited();
        dgList.BFS();

        dgList.toplogicalSort();
        dgList.dijkstra(0);
    }
}
















